package graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class GraphByMatrix {

    private char[] arrayV;//顶点数组
    private int[][] matrix;//邻接矩阵
    private boolean isDirect;//是否是有向图

    /**
     * @param size 代表当前顶点的个数
     * @param isDirect
     */
    public GraphByMatrix(int size, boolean isDirect) {
        this.arrayV = new char[size];
        matrix = new int[size][size];
        //这里约定：统一初始化为最大值
        for(int i = 0; i < size; i++) {
            Arrays.fill(matrix[i], Constant.MAX);
        }
        this.isDirect = isDirect;
    }

    /**
     * 初始化顶点
     * @param array
     */
    public void initArrayV(char[] array) {
        for(int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     * 增加边
     * @param srcV 起点
     * @param destV 终点
     * @param weight 权值
     */
    public void addEdge(char srcV, char destV, int weight) {
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);

        matrix[srcIndex][destIndex] = weight;
        //如果是无向图，那么相反的位置，也同样需要置为空
        if(!isDirect) {
            matrix[destIndex][srcIndex] = weight;
        }
    }

    /**
     * 获取顶点的下标
     * @param v
     * @return
     */
    private int getIndexOfV(char v) {
        for(int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == v)
            return i;
        }
        return -1;
    }

    /**
     * 获取顶点的度，有向图 = 入度 + 出度
     * @return
     */
    public int getDevofV(char v) {
        int count = 0;
        int srcIndex = getIndexOfV(v);
        for(int i = 0; i < arrayV.length; i++) {
            if(matrix[srcIndex][i] != Constant.MAX) {
                count++;
            }
        }

        //计算有向图的入度
        if(isDirect) {
            for(int i = 0; i < arrayV.length; i++) {
                if(matrix[i][srcIndex] != Constant.MAX) {
                    count++;
                }
            }
        }
        return count;
    }

    //打印数组
    public void printGraph() {
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] == Constant.MAX) {
                    System.out.print("∞ ");
                } else {
                    System.out.print(matrix[i][j] + " ");
                }
            }
            System.out.println();
        }
    }


    //广度优先遍历
    public void bfs(char v) {
        //数组用来标记顶点是否被使用过
        boolean[] visited = new boolean[arrayV.length];

        //定义一个队列，来辅助完成 bfs
        Queue<Integer> queue = new LinkedList<>();
        int srcIndex = getIndexOfV(v);
        queue.offer(srcIndex);
        while(!queue.isEmpty()) {
            int top = queue.poll();
            System.out.print(arrayV[top] + "->");
            visited[top] = true;//每次弹出一个元素就置为 true
            for(int i = 0; i < arrayV.length; i++) {
                if(matrix[top][i] != Constant.MAX && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;//每次入队就置为true
                }
            }
        }
    }

    // 深度优先遍历
    public void dfs(char v) {
        //数组用来标记顶点是否被使用过
        boolean[] visited = new boolean[arrayV.length];
        int srcIndex = getIndexOfV(v);
        dfsChild(srcIndex, visited);
    }

    private void dfsChild(int srcIndex, boolean[] visited) {
        System.out.print(arrayV[srcIndex] + "->");
        visited[srcIndex] = true;
        for(int i = 0; i < arrayV.length; i++) {
            if(matrix[srcIndex][i] != Constant.MAX && !visited[i]) {
                dfsChild(i, visited);
            }
        }
    }

    //测试
    public static void main(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4, false);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.initArrayV(array);

        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);

//        graph.bfs('B');
        graph.dfs('B');
    }
}
